{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Network Delay Time"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #depth-first-search #breadth-first-search #graph #shortest-path #heap-priority-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #深度优先搜索 #广度优先搜索 #图 #最短路 #堆（优先队列）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: networkDelayTime"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #网络延迟时间"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>有 <code>n</code> 个网络节点，标记为&nbsp;<code>1</code>&nbsp;到 <code>n</code>。</p>\n",
    "\n",
    "<p>给你一个列表&nbsp;<code>times</code>，表示信号经过 <strong>有向</strong> 边的传递时间。&nbsp;<code>times[i] = (u<sub>i</sub>, v<sub>i</sub>, w<sub>i</sub>)</code>，其中&nbsp;<code>u<sub>i</sub></code>&nbsp;是源节点，<code>v<sub>i</sub></code>&nbsp;是目标节点， <code>w<sub>i</sub></code>&nbsp;是一个信号从源节点传递到目标节点的时间。</p>\n",
    "\n",
    "<p>现在，从某个节点&nbsp;<code>K</code>&nbsp;发出一个信号。需要多久才能使所有节点都收到信号？如果不能使所有节点收到信号，返回&nbsp;<code>-1</code> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2019/05/23/931_example_1.png\" style=\"height: 220px; width: 200px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2\n",
    "<strong>输出：</strong>2\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>times = [[1,2,1]], n = 2, k = 1\n",
    "<strong>输出：</strong>1\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>times = [[1,2,1]], n = 2, k = 2\n",
    "<strong>输出：</strong>-1\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= k &lt;= n &lt;= 100</code></li>\n",
    "\t<li><code>1 &lt;= times.length &lt;= 6000</code></li>\n",
    "\t<li><code>times[i].length == 3</code></li>\n",
    "\t<li><code>1 &lt;= u<sub>i</sub>, v<sub>i</sub> &lt;= n</code></li>\n",
    "\t<li><code>u<sub>i</sub> != v<sub>i</sub></code></li>\n",
    "\t<li><code>0 &lt;= w<sub>i</sub> &lt;= 100</code></li>\n",
    "\t<li>所有 <code>(u<sub>i</sub>, v<sub>i</sub>)</code> 对都 <strong>互不相同</strong>（即，不含重复边）</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [network-delay-time](https://leetcode.cn/problems/network-delay-time/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [network-delay-time](https://leetcode.cn/problems/network-delay-time/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[2,1,1],[2,3,1],[3,4,1]]\\n4\\n2', '[[1,2,1]]\\n2\\n1', '[[1,2,1]]\\n2\\n2']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:\n",
    "        graph = [[] for _ in range(n + 1)]\n",
    "        for edge in times:\n",
    "            fr, to, weight = edge\n",
    "            graph[fr].append([to, weight])\n",
    "        dist_to = self.djkstra(graph, k)\n",
    "        res = 0\n",
    "        for d in dist_to:\n",
    "            if d == float(\"inf\"):\n",
    "                return -1\n",
    "            res = max(res, d)\n",
    "        return res\n",
    "\n",
    "    def djkstra(self, graph, start):\n",
    "        class State:\n",
    "            def __init__(self, id, dist_from_start):\n",
    "                self.id = id\n",
    "                self.dist_from_start = dist_from_start\n",
    "\n",
    "            def __lt__(self, other):\n",
    "                return self.dist_from_start < other.dist_from_start\n",
    "\n",
    "        dist_to = [float(\"inf\")] * len(graph)\n",
    "        dist_to[start] = 0\n",
    "\n",
    "        pq = []\n",
    "        heapq.heappush(pq, State(start, 0))\n",
    "\n",
    "        while pq:\n",
    "            cur = heapq.heappop(pq)\n",
    "            cur_id = cur.id\n",
    "            cur_dist_from_start = cur.dist_from_start\n",
    "            if cur_dist_from_start > dist_to[cur_id]:\n",
    "                continue\n",
    "\n",
    "            for neighbor in graph[cur_id]:\n",
    "                next_id = neighbor[0]\n",
    "                next_dist = dist_to[cur_id] + neighbor[1]\n",
    "\n",
    "                if dist_to[next_id] > next_dist:\n",
    "                    dist_to[next_id] = next_dist\n",
    "                    heapq.heappush(pq, State(next_id, dist_to[next_id]))\n",
    "        return dist_to[1:]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def networkDelayTime(self, times, N, K):\n",
    "        vis = set()\n",
    "        INF, minV = 10000, K\n",
    "        dis = {i+1:INF for i in range(N)}\n",
    "        dis[K] = 0\n",
    "        G = {i+1:{} for i in range(N)}\n",
    "        for time in times:\n",
    "            G[time[0]][time[1]] = time[2]\n",
    "        \n",
    "        for _ in range(N):\n",
    "            vis.add(minV)\n",
    "            for k, v in G[minV].items():\n",
    "                dis[k] = min(dis[k], dis[minV] + v)\n",
    "                \n",
    "            new = INF\n",
    "            for v in range(1, N+1):\n",
    "                if v not in vis:\n",
    "                    if new > dis[v]:\n",
    "                        new = dis[v]\n",
    "                        minV = v\n",
    "        \n",
    "        max_time = dis[K]\n",
    "        for v, dist in dis.items():\n",
    "            max_time = max(max_time, dist)\n",
    "        return max_time if max_time != INF else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def networkDelayTime(self, times, num, source):\n",
    "        \"\"\"\n",
    "        :type times: List[List[int]]\n",
    "        :type num: int\n",
    "        :type source: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        #Dijstras's algorithm use heap\n",
    "        graph = [[] for i in range(num)]\n",
    "        for u, v, w in times:\n",
    "            graph[u - 1].append((v - 1, w))\n",
    "        dis = [1048576] * num # would be INF in this problem\n",
    "        dis[source - 1] = 0\n",
    "        que = [(0, source - 1)]\n",
    "        while que:\n",
    "            d, u = heapq.heappop(que)\n",
    "            if d > dis[u]:\n",
    "                continue\n",
    "            for v, w in graph[u]:\n",
    "                if dis[v] > d + w:\n",
    "                    dis[v] = d + w\n",
    "                    heapq.heappush(que, (dis[v], v))\n",
    "        ans = max(dis)\n",
    "        return ans if ans < 1048576 else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def networkDelayTime(self, times, N, K):\n",
    "        \"\"\"\n",
    "        :type times: List[List[int]]\n",
    "        :type N: int\n",
    "        :type K: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        h = [(0, K)]\n",
    "        res = 0\n",
    "        reached = set()\n",
    "        d = {}\n",
    "        for u, v, w in times:\n",
    "            if u not in d:\n",
    "                d[u] = []\n",
    "            d[u].append([v, w])\n",
    "        while h:\n",
    "            t, n = heapq.heappop(h)\n",
    "            if n not in reached:\n",
    "                res = t\n",
    "                reached.add(n)\n",
    "            if n in d:\n",
    "                for v, w in d[n]:\n",
    "                    if v not in reached:\n",
    "                        heapq.heappush(h, [t + w, v])\n",
    "        if len(reached) < N:\n",
    "            return -1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "from queue import *\n",
    "class Solution:\n",
    "    def networkDelayTime(self, times: 'List[List[int]]', N: 'int', K: 'int') -> 'int':\n",
    "        '''\n",
    "        Inf = 1e10\n",
    "        graph = collections.defaultdict(list)\n",
    "        for u, v, w in times:\n",
    "            graph[u - 1].append((v - 1, w))\n",
    "        V = [K - 1]\n",
    "        T = [1 for i in range(N)]\n",
    "        T[K - 1] = 0\n",
    "        dist = [Inf] * N\n",
    "        dist[K - 1] = 0\n",
    "        \n",
    "        while(1 in T):\n",
    "            node =  V[-1]\n",
    "            mindis = Inf\n",
    "            u = V[-1]\n",
    "            for v, w in graph[node]:\n",
    "                if dist[node] + w < dist[v]:\n",
    "                    dist[v] = dist[node] + w\n",
    "            for i in range(N):\n",
    "                if T[i] == 1 and dist[i] < mindis:\n",
    "                    mindis = dist[i]\n",
    "                    u = i\n",
    "            if mindis == Inf:\n",
    "                return -1\n",
    "            #print(u)\n",
    "            V.append(u)\n",
    "            T[u] = 0\n",
    "        if Inf in dist:\n",
    "            return -1\n",
    "        else:\n",
    "            return max(dist)\n",
    "        \n",
    "        edges = [[9e6]*N for i in range(N)]\n",
    "        for e in times:\n",
    "            edges[e[0]-1][e[1]-1] = e[2] \n",
    "        dis = [9e6 for _ in range(N)]\n",
    "        for i in range(N):\n",
    "            edges[i][i] = 0\n",
    "            if edges[K-1][i] != 9e6:\n",
    "                dis[i] = edges[K-1][i]\n",
    "        flag = [0 for _ in range(N)]\n",
    "        flag[K-1] = 1\n",
    "        for i in range(N-1):\n",
    "            min_dis = 9e6\n",
    "            for j in range(N):\n",
    "                if flag[j] == 0 and dis[j] < min_dis:\n",
    "                    min_dis = dis[j]\n",
    "                    u = j\n",
    "            if min_dis == 9e6:\n",
    "                return -1\n",
    "            flag[u] = 1\n",
    "            for v in range(N):\n",
    "                if edges[u][v]!= 9e6:\n",
    "                    if dis[v] > dis[u]+edges[u][v]:\n",
    "                        dis[v] = dis[u]+edges[u][v]\n",
    "        if 9e6 in dis:\n",
    "            return -1\n",
    "        else:\n",
    "            return sorted(dis)[-1]\n",
    "        '''\n",
    "        INF = 0x7FFFFFFF\n",
    "        adj = collections.defaultdict(list)\n",
    "        \n",
    "        q = PriorityQueue()\n",
    "\n",
    "        dist = [INF] * (N)\n",
    "        visit = []\n",
    "\n",
    "\n",
    "        for u, v, w in times:\n",
    "            adj[u - 1].append((v - 1, w))\n",
    "\n",
    "        dist[K - 1] = 0\n",
    "        q.put((dist[K - 1],K - 1))          \n",
    "\n",
    "\n",
    "        while not q.empty():\n",
    "            MIN, node = q.get()\n",
    "            if node not in visit:\n",
    "                visit.append(node)\n",
    "            else:\n",
    "                continue\n",
    "            for v, w in adj[node]:\n",
    "                if MIN + w < dist[v]:\n",
    "                    dist[v] = MIN + w\n",
    "                    q.put((dist[v],v))\t\t\n",
    "        return max(dist) if len(visit) == N else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# https://leetcode-cn.com/problems/network-delay-time/description/\n",
    "from queue import PriorityQueue\n",
    "\n",
    "\n",
    "class Node(object):\n",
    "    index = None\n",
    "    weight = None\n",
    "\n",
    "    def __init__(self, index, weight):\n",
    "        self.index = index\n",
    "        self.weight = weight\n",
    "\n",
    "    def __lt__(self, other):\n",
    "        return self.weight < other.weight\n",
    "\n",
    "    def __eq__(self, other):\n",
    "        return self.weight == other.weight\n",
    "\n",
    "    def __repr__(self):\n",
    "        return 'Index: {}, weight: {}'.format(self.index, self.weight)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def networkDelayTime(self, times, N, K):\n",
    "        \"\"\"\n",
    "        :type times: List[List[int]]\n",
    "        :type N: int\n",
    "        :type K: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "\n",
    "        edgesData = [[] for _ in range(N + 1)]\n",
    "\n",
    "        for item in times:\n",
    "            start = item[0]\n",
    "            edgesData[start].append(item)\n",
    "\n",
    "        maxV = float('+inf')\n",
    "        weights = [maxV] * (N + 1)\n",
    "        weights[K] = 0\n",
    "\n",
    "        pQueue = PriorityQueue()\n",
    "        pQueue.put(Node(K, 0))\n",
    "\n",
    "        marked = set()\n",
    "        while not pQueue.empty():\n",
    "            node = pQueue.get()\n",
    "            index = node.index\n",
    "            if index in marked:\n",
    "                continue\n",
    "            marked.add(index)\n",
    "            weight = weights[index]\n",
    "\n",
    "            for edge in edgesData[index]:\n",
    "                toPoint = edge[1]\n",
    "                if weight + edge[2] < weights[toPoint]:\n",
    "                    weights[toPoint] = weight + edge[2]\n",
    "                pQueue.put(Node(toPoint, weights[toPoint]))\n",
    "\n",
    "        result = 0\n",
    "        for i in range(1, N + 1):\n",
    "            if weights[i] == maxV:\n",
    "                return -1\n",
    "            result = max(result, weights[i])\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def networkDelayTime(self, times, N, K):\n",
    "        \"\"\"\n",
    "        :type times: List[List[int]]\n",
    "        :type N: int\n",
    "        :type K: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        h = [(0, K)]\n",
    "        res = 0\n",
    "        reached = set()\n",
    "        d = {}\n",
    "        for u, v, w in times:\n",
    "            if u not in d:\n",
    "                d[u] = []\n",
    "            d[u].append([v, w])\n",
    "        while h:\n",
    "            t, n = heapq.heappop(h)\n",
    "            if n not in reached:\n",
    "                res = t\n",
    "                reached.add(n)\n",
    "                if n in d:\n",
    "                    for v, w in d[n]:\n",
    "                        if v not in reached:\n",
    "                            heapq.heappush(h, [t + w, v])\n",
    "        if len(reached) < N:\n",
    "            return -1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import pprint\n",
    "class Solution:\n",
    "    def networkDelayTime(self, times, N, K):\n",
    "        \"\"\"\n",
    "        :type times: List[List[int]]\n",
    "        :type N: int\n",
    "        :type K: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        inf = 0x7FFFFFFF\n",
    "        edges = [[inf for _ in range(N + 1)] for _ in range(N + 1)]\n",
    "        dist = [inf] * (N + 1)\n",
    "        visit = [False] * (N + 1)\n",
    "\n",
    "        # initialize the times\n",
    "        for t in times:\n",
    "            edges[t[0]][t[1]] = t[2]\n",
    "        pprint.pprint(edges)\n",
    "        # dist[K] is set to 0, because point K is the start point, hence the distance to itself is 0\n",
    "        dist[K] = 0\n",
    "        # at most loops N times to visit each point, including the start point itself\n",
    "        # if no point is found, then return with -1\n",
    "        for i in range(N):\n",
    "            MIN = inf\n",
    "            index = None\n",
    "            # find a point\n",
    "            for j in range(N + 1):\n",
    "                if visit[j] == False and dist[j] < MIN:\n",
    "                    MIN = dist[j]\n",
    "                    index = j\n",
    "            # if no point can be found, then return with -1\n",
    "            if index is None:\n",
    "                return -1\n",
    "            # else the point is visited, then change the label, and it won't be visited next time\n",
    "            visit[index] = True\n",
    "            for j in range(N + 1):\n",
    "                if visit[j] == False and MIN + edges[index][j] < dist[j]:\n",
    "                    dist[j] = MIN + edges[index][j]\n",
    "\n",
    "        return max(dist[1:])\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def networkDelayTime(self, times, N, K):\n",
    "        \"\"\"\n",
    "        :type times: List[List[int]]\n",
    "        :type N: int\n",
    "        :type K: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        direct, length, ans, pq = collections.defaultdict(list), {}, [None] * N, [[0, K]]\n",
    "        for u, v, w in times:\n",
    "            direct[u].append(v)\n",
    "            length[(u, v)] = w\n",
    "        while pq:\n",
    "            cur = heapq.heappop(pq)\n",
    "            if ans[cur[1] - 1] is None:\n",
    "                ans[cur[1] - 1] = cur[0]\n",
    "                for v in direct[cur[1]]:\n",
    "                    if ans[v - 1] is None:\n",
    "                        heapq.heappush(pq, [cur[0] + length[(cur[1], v)], v])\n",
    "        # print(ans)\n",
    "        return max(ans) if all(a is not None for a in ans) else -1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def networkDelayTime(self, times, N, K):\n",
    "        \"\"\"\n",
    "        :type times: List[List[int]]\n",
    "        :type N: int\n",
    "        :type K: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        # d算法\n",
    "        weight = {}\n",
    "        graph = collections.defaultdict(list)\n",
    "        for u, v, w in times:\n",
    "            weight[(u,v)] = w\n",
    "            graph[u].append(v)\n",
    "        ans = [1<<31]*N\n",
    "        ans[K-1] = 0\n",
    "        remain = {i for i in range(1, N+1)}\n",
    "        while remain:\n",
    "            index = 0\n",
    "            for node in remain:\n",
    "                if index == 0:\n",
    "                    index = node\n",
    "                else:\n",
    "                    if ans[node-1] < ans[index-1]:\n",
    "                        index = node\n",
    "            remain.discard(index)\n",
    "            for nei in graph[index]:\n",
    "                if nei in remain:\n",
    "                    if ans[nei-1] > ans[index-1] + weight[(index, nei)]:\n",
    "                        ans[nei-1] = ans[index-1] + weight[(index, nei)]\n",
    "        temp = max(ans)\n",
    "        if temp == (1<<31):\n",
    "            return -1\n",
    "        else:\n",
    "            return temp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def networkDelayTime(self, times: List[List[int]], N: int, K: int) -> int:\n",
    "        d = [{} for _ in range(N + 1)]\n",
    "        for i, j, k in times:\n",
    "            d[i][j] = k\n",
    "        v = [0] + [float('inf')] * N\n",
    "        v[K], q = 0, collections.deque([K])\n",
    "        while q:\n",
    "            i = q.popleft()\n",
    "            for j in d[i]:\n",
    "                if v[i] + d[i][j] < v[j]:\n",
    "                    v[j] = v[i] + d[i][j]\n",
    "                    q.append(j)\n",
    "        ans = max(v)\n",
    "        return [-1, ans][ans < float('inf')]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def networkDelayTime(self, times: List[List[int]], N: int, K: int) -> int:\n",
    "        map_matrix = [[-1] * (N + 1) for i in range(N + 1)]\n",
    "        value_des = [-1 for i in range(N + 1)]\n",
    "        node_des = []\n",
    "        node_index = 0\n",
    "        max_length = -1\n",
    "        for item in times:\n",
    "            map_matrix[item[0]][item[1]] = item[2]\n",
    "        for a in range(N+1)[1:]:\n",
    "            for b in range(N+1)[1:]:\n",
    "                for c in range(N+1)[1:]:\n",
    "                    if map_matrix[a][b] == -1 or map_matrix[b][c] == -1:\n",
    "                        continue\n",
    "                    if map_matrix[a][c] > map_matrix[a][b] + map_matrix[b][c]:\n",
    "                        map_matrix[a][c] = map_matrix[a][b] + map_matrix[b][c]\n",
    "                    if map_matrix[a][c] == -1:\n",
    "                        map_matrix[a][c] = map_matrix[a][b] + map_matrix[b][c]\n",
    "        node_des.append(K)\n",
    "        value_des[K] = 0\n",
    "        while True:\n",
    "            if node_index == len(node_des):\n",
    "                break\n",
    "            self.network_delay_circulation(map_matrix, node_des[node_index], node_des, value_des)\n",
    "            node_index += 1\n",
    "\n",
    "        for item in value_des[1:]:\n",
    "            if item == -1:\n",
    "                return -1\n",
    "            if max_length < item:\n",
    "                max_length = item\n",
    "\n",
    "        return max_length\n",
    "    def network_delay_circulation(self, map_matrix: [[]], k: int, node_des: [], value_des: []):\n",
    "        # print(\"k = \", end=\" \")\n",
    "        # print(k)\n",
    "        # print(\"node_des = \", end=\" \")\n",
    "        # print(node_des)\n",
    "        # print(\"value_des = \", end=\" \")\n",
    "        # print(value_des)\n",
    "        for index, value in enumerate(map_matrix[k]):\n",
    "            if value == -1:\n",
    "                continue\n",
    "\n",
    "            if index in node_des:\n",
    "                if value_des[index] > value_des[k] + map_matrix[k][index]:\n",
    "                    value_des[index] = value_des[k] + map_matrix[k][index]\n",
    "            else:\n",
    "                node_des.append(index)\n",
    "                value_des[index] = value_des[k] + map_matrix[k][index]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import sys\n",
    "from queue import PriorityQueue\n",
    "class Solution:\n",
    "    def networkDelayTime(self, times, N, K):\n",
    "        tm_lst = [0] + [sys.maxsize for i in range(N)]\n",
    "        cands = PriorityQueue()\n",
    "        cands.put([0, K])\n",
    "        while not cands.empty():\n",
    "            node = cands.get()\n",
    "            if tm_lst[node[1]] <= node[0]:\n",
    "                continue\n",
    "            tm_lst[node[1]] = node[0]\n",
    "            i = 0\n",
    "            while i < len(times):\n",
    "                if times[i][0] == node[1]:\n",
    "                    cands.put([times[i][2] + node[0], times[i][1]])\n",
    "                    times.pop(i)\n",
    "                else:\n",
    "                    i += 1\n",
    "        max_time = max(tm_lst)\n",
    "        if max_time == sys.maxsize:\n",
    "            return -1\n",
    "        else:\n",
    "            return max_time"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def networkDelayTime(self, times: List[List[int]], N: int, K: int) -> int:\n",
    "        import heapq\n",
    "\n",
    "        nodeToCandidate ={}\n",
    "        candidateList = []\n",
    "        # 保存节点的路径长度\n",
    "        nodeToPath = {}\n",
    "\n",
    "        candidateList.append([0,K])\n",
    "        nodeToCandidate[K] = candidateList[-1]\n",
    "        while len(candidateList) > 0:\n",
    "            il=  min(candidateList)\n",
    "            nodeToCandidate.pop(il[1])\n",
    "            candidateList.remove(il)\n",
    "            nodeToPath[il[1]] = il[0]\n",
    "\n",
    "            newNode = il[1]\n",
    "            newNodePath = il[0]\n",
    "            i = 0\n",
    "            while i < len(times):\n",
    "                if newNode == times[i][0]:\n",
    "                    v= times[i][1]\n",
    "                    w =  times[i][2]\n",
    "                    # 不是已经到达的节点\n",
    "                    if nodeToPath.get(v) is None:\n",
    "                        if nodeToCandidate.get(v) is None:\n",
    "                            candidateList.append([newNodePath+ w , v])\n",
    "\n",
    "                            nodeToCandidate[v] =candidateList[-1]\n",
    "                        elif newNodePath+ w<nodeToCandidate[v][0] :\n",
    "                            nodeToCandidate[v][0] =  newNodePath+ w\n",
    "                    times.pop(i)\n",
    "                else:\n",
    "                    i+=1\n",
    "\n",
    "\n",
    "        vl = list(nodeToPath.values())\n",
    "        return  max(vl) if len(vl) == N else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def networkDelayTime(self, times: List[List[int]], N: int, K: int) -> int:\n",
    "        shorted_times=[float('inf') for _ in range(N)]\n",
    "        arrived_node=[False for _ in range(N)]\n",
    "        arrived_node[K-1]=True\n",
    "        shorted_times[K-1]=0\n",
    "        cur_node=K-1\n",
    "        for _ in range(N-1):\n",
    "            pos=0\n",
    "            while pos<len(times):\n",
    "                if times[pos][0]-1==cur_node:\n",
    "                    shorted_times[times[pos][1]-1]=min([shorted_times[times[pos][1]-1],shorted_times[cur_node]+times[pos][2]])\n",
    "                    times.pop(pos)\n",
    "                else:\n",
    "                    pos+=1\n",
    "            new_min=float('inf')\n",
    "            next_node=N\n",
    "            for node in range(N):\n",
    "                if arrived_node[node]==False and shorted_times[node]<new_min:\n",
    "                    new_min=shorted_times[node]                \n",
    "                    next_node=node\n",
    "            if next_node==N:\n",
    "                return -1\n",
    "            arrived_node[next_node]=True\n",
    "            cur_node=next_node\n",
    "        return max(shorted_times)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import sys\n",
    "from queue import PriorityQueue\n",
    "class Solution:\n",
    "    def networkDelayTime(self, times, N, K):\n",
    "        tm_lst = [0] + [sys.maxsize for i in range(N)]\n",
    "        cands = PriorityQueue()\n",
    "        cands.put([0, K])\n",
    "        while not cands.empty():\n",
    "            node = cands.get()\n",
    "            if tm_lst[node[1]] <= node[0]:\n",
    "                continue\n",
    "            tm_lst[node[1]] = node[0]\n",
    "            i = 0\n",
    "            while i < len(times):\n",
    "                if times[i][0] == node[1]:\n",
    "                    cands.put([times[i][2] + node[0], times[i][1]])\n",
    "                    times.pop(i)\n",
    "                else:\n",
    "                    i += 1\n",
    "        max_time = max(tm_lst)\n",
    "        if max_time == sys.maxsize:\n",
    "            return -1\n",
    "        else:\n",
    "            return max_time"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def networkDelayTime(self, times: List[List[int]], N: int, K: int) -> int:\n",
    "\n",
    "        dist = {i: float('inf') for i in range(1, N+1)}\n",
    "        dist[K] = 0\n",
    "        res = {}\n",
    "        while dist:\n",
    "            min_dis = min(dist.values())\n",
    "            if min_dis == float('inf'):\n",
    "                return -1\n",
    "            for key, v in dist.items():\n",
    "                if v == min_dis:\n",
    "                    ind = key\n",
    "            for time in times:\n",
    "                if time[0] == ind and time[1] not in res.keys():\n",
    "                    dist[time[1]] = min(dist[time[1]], dist[time[0]]+time[2])\n",
    "            res[ind] = min_dis\n",
    "            dist.pop(ind)\n",
    "        return max(res.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#######################################################################\n",
    "## kongconf 2020-12-11\n",
    "#######################################################################\n",
    "class Solution:\n",
    "    def networkDelayTime(self, times: List[List[int]], N: int, K: int) -> int:\n",
    "        MAX = 6000000\n",
    "        floyd = [[MAX for _ in range(N + 1)] for _ in range(N + 1)]\n",
    "        for i in range(N + 1):\n",
    "            floyd[i][i] = 0\n",
    "        for t in times:\n",
    "            floyd[t[0]][t[1]] = t[2]\n",
    "        for k in range(1, N + 1):\n",
    "            for i in range(1, N + 1):\n",
    "                for j in range(1, N + 1):\n",
    "                    if floyd[i][k] + floyd[k][j] < floyd[i][j]:\n",
    "                        floyd[i][j] = floyd[i][k] + floyd[k][j]\n",
    "        ans = 0\n",
    "        for i in range(1, N + 1):\n",
    "            if ans < floyd[K][i]:\n",
    "                ans = floyd[K][i]\n",
    "        if ans >= MAX:\n",
    "            return -1\n",
    "        else:\n",
    "            return ans\n",
    "#######################################################################"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:\n",
    "        vset={k}\n",
    "        count=1\n",
    "        vdic={k:0}\n",
    "        while count<n:\n",
    "            i=0\n",
    "            mintime=101\n",
    "            while i<len(times):\n",
    "                if times[i][0] in vset and times[i][1] not in vset and vdic[times[i][0]]+times[i][2]<mintime:\n",
    "                    mintime=vdic[times[i][0]]+times[i][2]\n",
    "                    minnode=times[i][1]\n",
    "                elif times[i][0] in vset and times[i][1] in vset:\n",
    "                    times.pop(i)\n",
    "                    continue\n",
    "                i+=1\n",
    "            if mintime==101:\n",
    "                return -1\n",
    "            vset.add(minnode)\n",
    "            vdic[minnode]=mintime\n",
    "            count+=1\n",
    "        return mintime"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:\n",
    "        isRecv = [-1 for i in range(n)]\n",
    "        from queue import PriorityQueue\n",
    "        q = PriorityQueue()\n",
    "        q.put((0, k))\n",
    "        isRecv[k-1] = 0\n",
    "        res = 0\n",
    "        while not q.empty():\n",
    "            node = q.get()\n",
    "            i = 0\n",
    "            while i < len(times):\n",
    "                ele = times[i]\n",
    "                if node[1] == ele[0]:\n",
    "                    if(isRecv[ele[1]-1] == -1 or (node[0] + ele[2]) < isRecv[ele[1]-1]):\n",
    "                        q.put((node[0] + ele[2], ele[1]))\n",
    "                        isRecv[ele[1]-1] = node[0] + ele[2]\n",
    "                    times.remove(ele)\n",
    "                    i -= 1\n",
    "                i += 1\n",
    "        for ele in isRecv:\n",
    "            if ele == -1:\n",
    "                return -1\n",
    "            if ele > res:\n",
    "                res = ele\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#From 张梓涵\n",
    "class Solution:\n",
    "    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:\n",
    "        g = [[float('inf')] * n for _ in range(n)]\n",
    "        for x, y, time in times:\n",
    "            g[x - 1][y - 1] = time\n",
    "\n",
    "        dist = [float('inf')] * n\n",
    "        dist[k - 1] = 0\n",
    "        used = [False] * n\n",
    "        for _ in range(n):\n",
    "            x = -1\n",
    "            for y, u in enumerate(used):\n",
    "                if not u and (x == -1 or dist[y] < dist[x]):\n",
    "                    x = y\n",
    "            used[x] = True\n",
    "            for y, time in enumerate(g[x]):\n",
    "                dist[y] = min(dist[y], dist[x] + time)\n",
    "\n",
    "        ans = max(dist)\n",
    "        return ans if ans < float('inf') else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:\n",
    "        nodes = collections.defaultdict(list)\n",
    "        while times:\n",
    "            time = times.pop(0)\n",
    "            nodes[time[0]].append(time)\n",
    "        for i in range(1, n+1):\n",
    "            nodes[i].sort(key=lambda x: x[2])\n",
    "        db = [float('inf') for _ in range(n)]\n",
    "        db[k - 1] = 0\n",
    "        q = []\n",
    "        q.append(k)\n",
    "        while q:\n",
    "            node = q.pop(0)\n",
    "            if node in nodes:\n",
    "                sub_nodes = nodes.pop(node)\n",
    "                sub_nodes.sort(key=lambda x: x[2])\n",
    "                for sub_node in sub_nodes:\n",
    "                    if sub_node[1] != k and sub_node[2] + db[node - 1] < db[sub_node[1] - 1]:\n",
    "                        db[sub_node[1] - 1] = sub_node[2] + db[node - 1]\n",
    "                        if not q:\n",
    "                            q.append(sub_node[1])\n",
    "                        else:\n",
    "                            already = True\n",
    "                            for i in range(len(q)):\n",
    "                                if db[sub_node[1] - 1] < db[q[i] - 1]:\n",
    "                                    q.insert(i, sub_node[1])\n",
    "                                    already = False\n",
    "                                    break\n",
    "                            if already:\n",
    "                                q.append(sub_node[1])\n",
    "\n",
    "        if float('inf') in db:\n",
    "            return -1\n",
    "        return max(db)\n",
    "\n",
    "\n",
    "                \n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:\n",
    "        g = [[float('inf')] * n for _ in range(n)]\n",
    "        for x, y, time in times:\n",
    "            g[x - 1][y - 1] = time\n",
    "\n",
    "        dist = [float('inf')] * n\n",
    "        dist[k - 1] = 0\n",
    "        used = [False] * n\n",
    "        # used[k-1]=True\n",
    "        for _ in range(n):\n",
    "            x = -1\n",
    "            for y, u in enumerate(used):\n",
    "                if not u and (x == -1 or dist[y] < dist[x]):\n",
    "                    x = y\n",
    "            used[x] = True\n",
    "            for y, time in enumerate(g[x]):\n",
    "                dist[y] = min(dist[y], dist[x] + time)\n",
    "\n",
    "        ans = max(dist)\n",
    "        return ans if ans < float('inf') else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:\n",
    "        inf = float('inf')\n",
    "        g = [[inf] * (n + 1) for _ in range(n + 1)]\n",
    "        for x, y, z in times:\n",
    "            g[x][y] = min(g[x][y], z)\n",
    "        dist = [inf] * (n + 1)\n",
    "        dist[k] = 0\n",
    "        state = [False] * (n + 1)\n",
    "\n",
    "        for _ in range(n):\n",
    "            t = -1\n",
    "            for j in range(1, n + 1):\n",
    "                if (not state[j]) and (t == -1 or dist[j] < dist[t]):\n",
    "                    t = j\n",
    "            state[t] = True\n",
    "            for j in range(1, n + 1):\n",
    "                dist[j] = min(dist[j], dist[t] + g[t][j])\n",
    "        \n",
    "        ans = max(dist[1:])\n",
    "        return ans if ans != inf else -1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Dijkstra(object):\n",
    "    def __init__(self, G, defaultdist=float(\"inf\")):\n",
    "        self.defaultdist = defaultdist\n",
    "        assert type(G) == dict\n",
    "        for i in G:\n",
    "            assert type(G[i]) == dict\n",
    "            break\n",
    "        self.G = G\n",
    "    def __init_distance(self, startV:int)->dict:\n",
    "        assert startV in self.G\n",
    "        tempdist = {s: self.defaultdist for s in self.G}\n",
    "        tempdist[startV] = 0\n",
    "        return tempdist\n",
    "    def dij_for_V(self, V_start:int)->[dict,dict]:\n",
    "        pqueue = []\n",
    "        heappush(pqueue, (0, V_start))\n",
    "        seen = set()\n",
    "        parent = {V_start: None}\n",
    "        distance = self.__init_distance(V_start)\n",
    "        while len(pqueue) > 0:\n",
    "            pair = heappop(pqueue)\n",
    "            distV, vertex = pair[0], pair[1]\n",
    "            if vertex in seen:\n",
    "                continue\n",
    "            seen.add(vertex)\n",
    "            for w in self.G[vertex].keys():\n",
    "                newdist = distV + self.G[vertex][w]\n",
    "                if newdist < distance[w]:\n",
    "                    heappush(pqueue, (newdist, w))\n",
    "                    parent[w] = vertex\n",
    "                    distance[w] = newdist\n",
    "        return parent, distance\n",
    "\n",
    "class Solution:\n",
    "    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:\n",
    "        G = {i+1:dict() for i in range(n)}\n",
    "        for u,v,w in times:\n",
    "            G[u][v]=w\n",
    "        dijk = Dijkstra(G)\n",
    "        p,dis = dijk.dij_for_V(k)\n",
    "        if (a:=max(dis.values()))<10e8:\n",
    "            return a\n",
    "        else:\n",
    "            return -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:\n",
    "        delay_map = {}\n",
    "        for time in times:\n",
    "            if time[0] in delay_map:\n",
    "                delay_map[time[0]].append([time[1], time[2]])\n",
    "            else:\n",
    "                delay_map[time[0]] = [[time[1], time[2]]]\n",
    "        visit = {}\n",
    "        heap = []\n",
    "\n",
    "        #heapq.heappush(heap, (k,0))\n",
    "        heapq.heappush(heap, (0, k))\n",
    "\n",
    "        while(len(heap)>0):\n",
    "            #node, cost = heapq.heappop(heap) \n",
    "            cost, node = heapq.heappop(heap) \n",
    "            #print(node)\n",
    "            if node in visit:\n",
    "                continue\n",
    "            else:\n",
    "                visit[node] = cost\n",
    "                if len(visit) == n:\n",
    "                    break\n",
    "                for nerghbor in delay_map.get(node, []):\n",
    "                    #heapq.heappush(heap, (nerghbor[0], nerghbor[1] + visit[node]))\n",
    "                    heapq.heappush(heap, (nerghbor[1] + visit[node], nerghbor[0]))\n",
    "            #print(visit)\n",
    "        #print(visit)\n",
    "        if len(visit) < n:\n",
    "            return -1\n",
    "\n",
    "        v = list(visit.values())\n",
    "        return max(v)\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:\n",
    "        #bellman ford\n",
    "        d = [inf] * (n+1)\n",
    "        d[k] = 0\n",
    "        for _ in range(n):           \n",
    "            for time in times:\n",
    "                if d[time[1]] > d[time[0]] + time[2]:\n",
    "                    d[time[1]] = d[time[0]] + time[2]\n",
    "        return max(d[1:]) if max(d[1:]) != inf else -1\n",
    "\n",
    "        #dijkstra\n",
    "        \"\"\" dist = [inf]*(n+1)\n",
    "        dist[k] = 0\n",
    "        h = [(0,k)]\n",
    "        while h:\n",
    "            d,x = heappop(h)\n",
    "            if d > dist[x]:\n",
    "                continue\n",
    "            for time in times:#这里要优化，应该弄好邻接表，否则复杂度高。\n",
    "                if x == time[0]:\n",
    "                    new_d = dist[x] + time[2]\n",
    "                    if new_d < dist[time[1]]:\n",
    "                        dist[time[1]] = new_d\n",
    "                        heappush(h,(new_d,time[1]))\n",
    "        #print(dist)\n",
    "        return max(dist[1:]) if max(dist[1:]) != inf else -1 \"\"\"\n",
    "\n",
    "        #结合酒须醉修改dijkstra\n",
    "        \"\"\" dct = defaultdict(dict)\n",
    "        for u, v, w in times:\n",
    "            dct[u][v] = w\n",
    "        dist = [inf] * (n+1)\n",
    "        dist[k] = 0\n",
    "        stack = [[0,k]]\n",
    "        while stack:\n",
    "            d, i = heappop(stack)\n",
    "            if d > dist[i]:\n",
    "                continue\n",
    "            for j in dct[i]:\n",
    "                new_d = d + dct[i][j]\n",
    "                if new_d < dist[j]:\n",
    "                    dist[j] = new_d\n",
    "                    heappush(stack,[new_d,j])\n",
    "        return max(dist[1:]) if max(dist[1:]) != inf else -1 \"\"\"\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:\n",
    "        dis = [float('INF')] * (n + 1)\n",
    "        dis[k] = 0\n",
    "        queue = [k]\n",
    "        while queue:\n",
    "            cur = queue.pop(0)\n",
    "            for i in range(len(times)):\n",
    "                tmp = times[i]\n",
    "                if tmp[0] == cur:\n",
    "                    tmp_dis =  dis[cur] + tmp[2]\n",
    "                    if tmp_dis<dis[tmp[1]]:\n",
    "                        dis[tmp[1]] = tmp_dis\n",
    "                        queue.append(tmp[1])\n",
    "        return max(dis[1:]) if max(dis[1:])!=float(\"INF\")  else -1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:\n",
    "\n",
    "        graph = [[] for _ in range(n)]\n",
    "        for time in times:\n",
    "            graph[time[0] - 1].append([time[1] - 1, time[2]])\n",
    "\n",
    "        distTo = [0] * n\n",
    "        for i in range(n):\n",
    "            distTo[i] = float(\"inf\")\n",
    "        distTo[k-1] = 0\n",
    "\n",
    "        pq = []\n",
    "\n",
    "        heapq.heappush(pq, [0, k-1])\n",
    "\n",
    "        while pq:\n",
    "            w, s = heapq.heappop(pq)\n",
    "            if w > distTo[s]:\n",
    "                continue\n",
    "            \n",
    "            for ne in graph[s]:\n",
    "                node, ne_w = ne[0], ne[1]\n",
    "                new_distance = distTo[s] + ne_w\n",
    "                if distTo[node] > new_distance:\n",
    "                    distTo[node] = new_distance\n",
    "                    heapq.heappush(pq, [new_distance, node])\n",
    "        res = 0\n",
    "        for i in distTo:\n",
    "            if i == float(\"inf\"):\n",
    "                return -1\n",
    "            res = max(res, i)\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for u, v, time in times:\n",
    "            g[u-1].append((v-1, time))\n",
    "        \n",
    "        dist = [float('inf')] * n\n",
    "        dist[k-1] = 0\n",
    "        que = [(0, k-1)]  # visted node\n",
    "        while que:\n",
    "            time, x = heapq.heappop(que)\n",
    "            if dist[x] < time:\n",
    "                continue\n",
    "            for y, time in g[x]:\n",
    "                d = dist[x] + time\n",
    "                if d < dist[y]:\n",
    "                    dist[y] = d\n",
    "                    heapq.heappush(que, (d,y))\n",
    "        \n",
    "        ans = max(dist)\n",
    "        return ans if ans < float('inf') else -1\n",
    "        "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
